import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024 —04 —10
 * Time: 19:25
 */  //根，节点，节点的度，左子树，右子树，深度，层数，叶节点
/*
 * 前序遍历：根左子树右，中序遍历：左中右，后序遍历：左右中
 * 满二叉树，2^0，2^1最后一层按顺序来。完全二叉树每一层都是满的
 * 四个结论
 * 1：根节点的层数为1，非空二叉树的第i层最多有2^（i-1）个节点
 * 2：只有根节点的二叉树的深度为1，那么二叉树最多有2^（k-1）个节点
 * 3：叶节点个数=N0  度为二的节点的个数为N2    N0 = N2 +1
 * 4：有n个节点的二叉树的深度K     2^(k -1） = n     取对数再取整
 * 5：n个节点，根节点序号为0，从上到下从左到右编号，
 * 有结论  第i个节点的左子树：2i+1 右子树：2i+2 （都要小于n）父节点（i-1）/2
 * */
public class BinaryTree {
    //内部类
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    //创建二叉树
    public TreeNode createdTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;

        return A;
    }
    void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    void preOrderNor(TreeNode root){
        if(root == null){
            return ;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) { //这一个条件很关键，就是current为空，栈不为空，就走右树
            while (current != null) {
                stack.push(current);
                System.out.print(current.val + " ");
                current = current.left;
            }
            TreeNode top = stack.pop();  // 一个个往外弹很好理解
            current = top.right;
        }
        return ;
    }

    void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }
    void  inOrderNor(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val);
            current = top.right;
        }
        return ;
    }

    void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);

    }
    void postOrderNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode pre = null;
        while (current != null || !stack.isEmpty()) { //对应124行，当左树一直走完了，current==null后得走右树了，所以多加一个条件就是判断栈是否为空
            while (current != null) {
                stack.push(current);
                current = current.left; //对应的这一句
            }
            TreeNode top = stack.peek();
            if (top.right == null  || top.right == pre){   //条件是top的右边还为null吗，为空就说明走完了
                System.out.print(top.val + " ");
                stack.pop();          //current = D , current != null ，curren =left = null,    (124跳130)current = K
                pre = top;//current==K的时候，不为空，进栈top=K，左右树都为null，当前current = null （左树），再往下走sout.val，在出栈K，重新循环后，
            }else {
                current = top.right;
            }
        }
    }

    //链表实现BineryTree
    public List<Character> preorderTraversal(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }
        ret.add(root.val);
       List<Character> leftTree = preorderTraversal(root.left);
       ret.addAll(leftTree);

       List<Character> riGhtTree = preorderTraversal(root.right);
        ret.addAll(riGhtTree);
        return ret;
    }
    public int nodeSize;
    int size1(BinaryTree.TreeNode root){
        if (root == null){
            return 0;
        }
        nodeSize++;
        size1(root.left);
        size1(root.right);
        return nodeSize;
    }

    int size2(BinaryTree.TreeNode root){
        //获取二叉树的节点个数：左子树的节点个数+右子树的节点个数+1
        if(root == null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }

    public int leafSize;

    int getLeafNodeCount1(BinaryTree.TreeNode root){
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return leafSize++ ;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
        return leafSize;

    }
    int getLeafNodeCount2(BinaryTree.TreeNode root){
        //子问题思路
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1 ;
        }
        return  getLeafNodeCount2(root.left)+ getLeafNodeCount2(root.right);

    }


    int getKLevelNodeCount(BinaryTree.TreeNode root , int k){
        //获取二叉树第k层的节点数
        if(root == null){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left , k-1) +
                getKLevelNodeCount(root.right , k-1);//不能写成k--
    }

    int getHeight1(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight1(root.left);
        int rightHeight = getHeight1(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    int getHeight2(TreeNode root){
        if (root == null){
            return 0;
        }
        return getHeight2(root.left) > getHeight2(root.right)
                ? getHeight2(root.left) + 1 : getHeight2(root.right) + 1;//判断的时候有一次时间复杂度为n，返回的时候又有一次时间复杂度wein
    }
    TreeNode find(TreeNode root , char val){
        if(root == null){//如果第一个root根为null  返回null
            return root;
        }
        if (root.val == val){
            return root;   //返回的时候，先找到的那个值给root，root再返回给leftroot,不为空，再走if语句返回leftroot
        }
        TreeNode leftroot = find(root.left , val);
        if (leftroot != null){
            return leftroot;  // 一直往左边走
        }
        TreeNode rightroot = find(root.right , val);
        if(rightroot != null){
            return rightroot; //一直往右边走
        }
        return null;//没找到
    }

    //层序遍历
    void levelOrder1(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(  !queue.isEmpty()  ){
            TreeNode current = queue.poll();
            System.out.print(current.val + " ");
            if(current.left  != null){
                queue.offer(current.left);//树节点为空了，还往队列里放就会报空指针异常
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
    }/*
    1：先创建队列
    2：*/
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList();//1创立队列
        queue.offer(root);//2：扔节点
        while(  !queue.isEmpty()  ){
            int size = queue.size();//4定义size（出的次数）
            List<Character> tem = new ArrayList<>();//6：定义一个一维数组

            while(size != 0){
                TreeNode current = queue.poll();//3：出节点？出几次>>定义size，出的次数为队列长度
                tem.add(current.val);//5：要把值放到一维数组里面？
                System.out.print(current.val + " "); //7打印一维数组里面的值
                size--;//8
                if(current.left  != null){//最后每出一个节点记为current，同时放此节点的两个子树进队列
                    queue.offer(current.left);//树节点为空了，还往队列里放就会报空指针异常
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            ret.add(tem);//这一句很重要啊，当每一层的节点在队列里都出完之后，把这一层（一维数组添加进二维数组里面）
        }
        return ret;//最后返回二维数组
    }
    boolean isCompleteTree(TreeNode root){
        if(root == null ){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode current = queue.poll();
            if(current== null){                        //这里的架构自己再写一遍也出问题了，current是谁要定义清楚，怎么出，什么条件下停止出队，
                                                          //出到null时候break
                break;//以这条语句结束这个while循环，说明现在出的元素为null
            }else{
                queue.offer(current.left);
                queue.offer(current.right);
            }
        }
        //判断队列里面是否含有非空元素
        while (!queue.isEmpty()){
            TreeNode temp = queue.peek();
            if (temp == null){
                queue.poll();   //这里自己又写了一遍有点问题，是null才出直到遇见非空
            }else{
                return false;
            }
        }
        return true;
    }



    /*236. 二叉树的最近公共祖先
     *
     * */

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution236 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            if(p == root || q == root){
                return root;//p，q中有一个在根节点
            }
            //从左边开始递归
            TreeNode leftTree = lowestCommonAncestor(root.left,p ,q);
            TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
            if(leftTree != null && rightTree != null){
                return root;
            }else if(leftTree != null ){
                return leftTree;
            }else{
                return rightTree;
            }
        }
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution236_2 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            Stack<TreeNode> stackP =new Stack<>();
            Stack<TreeNode> stackQ =new Stack<>();
            getPath(root,p,stackP);
            getPath(root,q,stackQ);
            int sizeP = stackP.size();
            int sizeQ = stackQ.size();

            if(sizeP > sizeQ){
                int size = sizeP - sizeQ;
                while(size != 0){
                    stackP.pop();
                    size--;
                }
            }
            if(sizeP < sizeQ){
                int size = sizeQ - sizeP;
                while(size != 0){
                    stackQ.pop();
                    size--;
                }
            }
            while(!stackP.isEmpty() && !stackQ.isEmpty()){
                if(stackP.peek() == stackQ.peek()){
                    return stackP.peek();
                }else{
                    stackP.pop();
                    stackQ.pop();
                }
            }
            return null;
        }
        /*关键方法——获取到达p/q的的路径*/
        private boolean getPath(TreeNode root , TreeNode Node , Stack<TreeNode> stack){
            if(root == null || Node == null){  //Node == null 这个条件可以不用，Node代表p或者q，谁没事在二叉树里面找null啊
                return false;
            }
            stack.push(root);
            //这里的push要放在下一个if语句前面，思考一下为啥？//懂了放后面如果if语句成立，直接就返回true了，栈里没有元素为空，还作个蛋的差//相当于少push了一次
            if(root == Node){  //这是一直递归到p或者q时发现的少了一句
                return true;
            }

            boolean flg1 = getPath(root.left , Node , stack);
            if(flg1){
                return true;
            }
            boolean flg2 = getPath(root.right , Node , stack);
            if(flg2){
                return true;
            }
            stack.pop();
            return false;
        }
    }

    /*
    * 606. 根据二叉树创建字符串*/
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution10 {
        public String tree2str(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            tree2strChild(root , stringBuilder);
            return stringBuilder.toString();

        }
        private void tree2strChild(TreeNode t , StringBuilder stringBuilder){
            if(t == null){
                return;
            }
            stringBuilder.append(t.val);
            if(t.left != null){
                stringBuilder.append("(");
                tree2strChild(t.left , stringBuilder);
                stringBuilder.append(")");  //前序遍历先把左子树走完
            }else{  //这里有两种情况是在t.left == null 的情况下   右树 =null 和 !null
                if(t.right == null){
                    return;   //返回30行
                } else{
                    stringBuilder.append("()");
                }
            }
            if(t.right != null){
                stringBuilder.append("(");
                tree2strChild(t.right , stringBuilder);
                stringBuilder.append(")");
            }else{
                return;  //t的右边为空就走完了直接return
            }

        }
    }



    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();//实例化外部类
        BinaryTree.TreeNode root = binaryTree.createdTree();//通过外部类点内部静态类   作为类型，调用方法，创建树，叫root

        System.out.print("打印初始二叉树："+"A B C D E F G");
        System.out.println();


        System.out.print("前序遍历：");
        binaryTree.preOrder(root);
        System.out.println();
        System.out.print("前序遍历2");
        binaryTree.preOrderNor(root);
        System.out.println();


        System.out.print("中序遍历非递归方法：");
        binaryTree.inOrder(root);
        System.out.println();
        System.out.print("中序遍历2非递归方法：");
        binaryTree.inOrderNor(root);
        System.out.println();


        System.out.print("后序遍历：");
        binaryTree.postOrder(root);
        System.out.println();
        System.out.print("后序遍历2非递归方法：");
        binaryTree.postOrderNor(root);
        System.out.println();


        System.out.print("通过顺序表实现二叉树的打印:");
        System.out.println(binaryTree.preorderTraversal(root));

        System.out.print("打印二叉树节点数"+"： ");
        System.out.println("普通思路二叉树节点数是" + binaryTree.size1(root) + " "+ "子问题思路结果是" + binaryTree.size2(root));

        System.out.print("打印叶子节点个数"+" : ");
        System.out.println("普通思路二叉树叶子节点个数是" + binaryTree.getLeafNodeCount1(root) + " " + "子问题思路结果是："+binaryTree.getLeafNodeCount2(root));

        System.out.println("二叉树第k层的节点个数是"+binaryTree.getKLevelNodeCount(root, 3));


        System.out.print("二叉树层序遍历结果为：");binaryTree.levelOrder1(root);
        System.out.println();
        System.out.print("方法2_二叉树层序遍历结果为：");binaryTree.levelOrder2(root);
        System.out.println();

        System.out.println("这棵二叉树是否是完全二叉树："+binaryTree.isCompleteTree(root));
        System.out.println();


    }



}






